#include "stdafx.h"
#include "astar_solver.h"
#include "bfs_move_gen.h"
#include "solve_puzzle.h"

/*
    iOS Game: Logic Games/Puzzle Set 11/Product Sentinels

    Summary
    Multiplicative Towers

    Description
    1. On the Board there are a few sentinels. These sentinels are marked with
       a number.
    2. The number tells you the product of the tiles that Sentinel can control
       (see) from there vertically and horizontally. This includes the tile 
       where he is located.
    3. You must put Towers on the Boards in accordance with these hints, keeping
       in mind that a Tower blocks the Sentinel View.
    4. The restrictions are that there must be a single continuous Garden, and
       two Towers can't touch horizontally or vertically.
    5. Towers can't go over numbered squares. But numbered squares don't block
       Sentinel View.
*/

namespace puzzles{ namespace ProductSentinels{

#define PUZ_SPACE        ' '
#define PUZ_EMPTY        '.'
#define PUZ_SENTINEL    'S'
#define PUZ_TOWER        'T'
#define PUZ_BOUNDARY    '+'

const Position offset[] = {
    {-1, 0},        // n
    {0, 1},        // e
    {1, 0},        // s
    {0, -1},        // w
};

struct puz_game
{
    string m_id;
    int m_sidelen;
    map<Position, int> m_pos2num;
    string m_start;

    puz_game(const vector<string>& strs, const xml_node& level);
};

puz_game::puz_game(const vector<string>& strs, const xml_node& level)
: m_id(level.attribute("id").value())
, m_sidelen(strs.size() + 2)
{
    m_start.append(m_sidelen, PUZ_BOUNDARY);
    for(int r = 1; r < m_sidelen - 1; ++r){
        auto& str = strs[r - 1];
        m_start.push_back(PUZ_BOUNDARY);
        for(int c = 1; c < m_sidelen - 1; ++c){
            auto s = str.substr(c * 2 - 2, 2);
            if(s == "  ")
                m_start.push_back(PUZ_SPACE);
            else{
                m_start.push_back(PUZ_SENTINEL);
                m_pos2num[{r, c}] = stoi(s);
            }
        }
        m_start.push_back(PUZ_BOUNDARY);
    }
    m_start.append(m_sidelen, PUZ_BOUNDARY);
}

struct puz_state
{
    puz_state() {}
    puz_state(const puz_game& g);
    int sidelen() const {return m_game->m_sidelen;}
    char cells(const Position& p) const { return m_cells[p.first * sidelen() + p.second]; }
    char& cells(const Position& p) { return m_cells[p.first * sidelen() + p.second]; }
    bool operator<(const puz_state& x) const { return m_matches < x.m_matches; }
    bool make_move(const Position& p, const vector<int>& perm);
    bool make_move2(const Position& p, const vector<int>& perm);
    int find_matches(bool init);

    //solve_puzzle interface
    bool is_goal_state() const {return get_heuristic() == 0;}
    void gen_children(list<puz_state>& children) const;
    unsigned int get_heuristic() const { return m_matches.size(); }
    unsigned int get_distance(const puz_state& child) const { return child.m_distance; }
    void dump_move(ostream& out) const {}
    ostream& dump(ostream& out) const;
    friend ostream& operator<<(ostream& out, const puz_state& state) {
        return state.dump(out);
    }

    const puz_game* m_game = nullptr;
    string m_cells;
    // key: the position of the number that represents the sentinel
    // value.elem: respective numbers of the tiles visible from the position of
    //             the sentinel in all the four directions
    map<Position, vector<vector<int>>> m_matches;
    unsigned int m_distance = 0;
};

puz_state::puz_state(const puz_game& g)
: m_cells(g.m_start), m_game(&g)
{
    for(auto& kv : g.m_pos2num)
        m_matches[kv.first];

    find_matches(true);
}

int puz_state::find_matches(bool init)
{
    for(auto& kv : m_matches){
        const auto& p = kv.first;
        auto& perms = kv.second;
        perms.clear();

        vector<vector<int>> dir_nums(4);
        for(int i = 0; i < 4; ++i){
            auto& os = offset[i];
            int n = 0;
            auto& nums = dir_nums[i];
            for(auto p2 = p + os; ; p2 += os){
                char ch = cells(p2);
                if(ch == PUZ_SPACE)
                    // we can stop here
                    nums.push_back(n++);
                else if(ch == PUZ_EMPTY || ch == PUZ_SENTINEL)
                    // we cannot stop here
                    ++n;
                else{
                    // we have to stop here
                    nums.push_back(n);
                    break;
                }
            }
        }

        int product = m_game->m_pos2num.at(p);
        // Compute the product of the tiles the sentinel can see from the position
        // Record the combination if the product is equal to the given number
        for(int n0 : dir_nums[0])
            for(int n1 : dir_nums[1])
                for(int n2 : dir_nums[2])
                    for(int n3 : dir_nums[3])
                        if((n0 + n2 + 1) * (n1 + n3 + 1) == product)
                            perms.push_back({n0, n1, n2, n3});

        if(!init)
            switch(perms.size()){
            case 0:
                return 0;
            case 1:
                return make_move2(p, perms.front()) ? 1 : 0;
            }
    }
    return 2;
}

struct puz_state2 : Position
{
    puz_state2(const puz_state& s);

    int sidelen() const { return m_state->sidelen(); }
    void make_move(const Position& p){ static_cast<Position&>(*this) = p; }
    void gen_children(list<puz_state2>& children) const;

    const puz_state* m_state;
};

puz_state2::puz_state2(const puz_state& s)
: m_state(&s)
{
    int i = boost::find_if(s.m_cells, [](char ch){
        return ch != PUZ_BOUNDARY && ch != PUZ_TOWER;
    }) - s.m_cells.begin();
    make_move({i / sidelen(), i % sidelen()});
}

void puz_state2::gen_children(list<puz_state2>& children) const
{
    for(auto& os : offset){
        auto p2 = *this + os;
        char ch = m_state->cells(p2);
        if(ch != PUZ_BOUNDARY && ch != PUZ_TOWER){
            children.push_back(*this);
            children.back().make_move(p2);
        }
    }
}

bool puz_state::make_move2(const Position& p, const vector<int>& perm)
{
    for(int i = 0; i < 4; ++i){
        auto& os = offset[i];
        int n = perm[i];
        auto p2 = p + os;
        for(int j = 0; j < n; ++j){
            char& ch = cells(p2);
            if(ch == PUZ_SPACE)
                ch = PUZ_EMPTY;
            p2 += os;
        }
        char& ch = cells(p2);
        if(ch == PUZ_SPACE){
            ch = PUZ_TOWER;
            // Two Towers can't touch horizontally or vertically
            for(auto& os2 : offset){
                char& ch2 = cells(p2 + os2);
                if(ch2 == PUZ_SPACE)
                    ch2 = PUZ_EMPTY;
            }
        }
    }

    ++m_distance;
    m_matches.erase(p);

    // There must be a single continuous garden
    list<puz_state2> smoves;
    puz_move_generator<puz_state2>::gen_moves(*this, smoves);
    return smoves.size() == boost::count_if(m_cells, [](char ch){
        return ch != PUZ_BOUNDARY && ch != PUZ_TOWER;
    });
}

bool puz_state::make_move(const Position& p, const vector<int>& perm)
{
    m_distance = 0;
    if(!make_move2(p, perm))
        return false;
    int m;
    while((m = find_matches(false)) == 1);
    return m == 2;
}

void puz_state::gen_children(list<puz_state>& children) const
{
    auto& kv = *boost::min_element(m_matches, [](
        const pair<const Position, vector<vector<int>>>& kv1,
        const pair<const Position, vector<vector<int>>>& kv2){
        return kv1.second.size() < kv2.second.size();
    });

    for(auto& perm : kv.second){
        children.push_back(*this);
        if(!children.back().make_move(kv.first, perm))
            children.pop_back();
    }
}

ostream& puz_state::dump(ostream& out) const
{
    for(int r = 1; r < sidelen() - 1; ++r) {
        for(int c = 1; c < sidelen() - 1; ++c){
            Position p(r, c);
            char ch = cells(p);
            if(ch == PUZ_SENTINEL)
                out << format("%2d") % m_game->m_pos2num.at(p);
            else
                out << ' ' << (ch == PUZ_SPACE ? PUZ_EMPTY : ch);
        }
        out << endl;
    }
    return out;
}

}}

void solve_puz_ProductSentinels()
{
    using namespace puzzles::ProductSentinels;
    solve_puzzle<puz_game, puz_state, puz_solver_astar<puz_state>>(
        "Puzzles/ProductSentinels.xml", "Puzzles/ProductSentinels.txt", solution_format::GOAL_STATE_ONLY);
}